//定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。 
//
// 
//
// 示例: 
//
// 输入: 1->2->3->4->5->NULL
//输出: 5->4->3->2->1->NULL 
//
// 
//
// 限制： 
//
// 0 <= 节点个数 <= 5000 
//
// 
//
// 注意：本题与主站 206 题相同：https://leetcode-cn.com/problems/reverse-linked-list/ 
//
// Related Topics 递归 链表 👍 582 👎 0

import leetcodeauto.common.ListNode;

//leetcode submit region begin(Prohibit modification and deletion)


/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode(int x) { val = x; }
 * }
 */

class SolutionO24_迭代
{
    public ListNode reverseList(ListNode head) {
        // 只管身前，莫问身后

        ListNode newHead = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextBack = curr.next;
            curr.next = newHead;
            newHead = curr;
            curr = nextBack;
        }

        return newHead;
    }
}


//leetcode submit region end(Prohibit modification and deletion)


class SolutionO24_draft {
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return head;
        }

        ListNode dyHead = null;
        ListNode curr = head;
        while (curr != null && curr.next != null) {
            ListNode first = curr;
            ListNode second = curr.next;
            curr = second.next;
            second.next = first;
            first.next = dyHead;
            dyHead = second;
        }
        if (curr != null && curr.next == null) {
            curr.next = dyHead;
            dyHead = curr;
        }

        return dyHead;
    }
}